#include <bits/stdc++.h>
using namespace std;
// int q;
// string x;
// string solve()
// {
//     cin>>x;
//     if(x%2==0)return to_string(x);
//     bool is=false;
//     vector<int> ret;
//     while(x)
//     {
//         int temp=x%10;
//         x/=10;
//         if(temp%2==0)is=true;
//         ret.push_back(temp);
//     }
//     if(is)
//     {
//         int temp=-1;
//         for(int i=0;i<ret.size();i++)
//         {
//             if(ret[i]%2==0)
//             {
//                 temp=i;
//                 break;
//             }
//         }
//         string s;
//         s+=to_string(ret[temp]);
//         for(int i=0;i<ret.size();i++)
//         {
//             //研究一下insert的行为，他会插入不进去数据
//             if(i!=temp)s.insert(s.begin(),ret[i]+'0');
//         }
//         while(!s.empty()&&s.front()=='0')s.erase(s.begin());

//         return s;
//     }
//     else return "-1";
// }
// int solve()
// {
//     cin>>x;
//     int i=stoi(x);
//     if(i%2==0)return i;
//     else
//     {
//         for(int i=0;i<x.size();i++)
//         {
//             //发现此数位的数字是偶数直接和最后一个数字交换即可
//             //不需要处理前导0，如果最后一个数字是0，那他一定是偶数，前面已经返回了
//             if(x[i]%2==0)
//             {
//                 swap(x[i],x.back());
//                 return stoi(x);
//             }
//         }
//     }
//     return -1;
// }
// int main()
// {
//     cin>>q;
//     while(q--)cout<<solve()<<endl;
//     return 0;
// }

// dfs/递归
// 画出决策树
//  int n;
//  int res;
//  void dfs(vector<int>&ret,vector<bool>&vis,int pos)
//  {
//      if(pos==n+1)
//      {
//          res++;
//          return;
//      }
//      for(int i=1;i<=n;i++)
//      {
//          if(vis[i])continue;
//          //转化问题，要求它在某个位置的前面，转化成
//          //这个点如果使用过，它的位置就无法更改，
//          //它想在某个位置的前面就不能满足
//          if(vis[ret[i]])return;
//          vis[i]=true;
//          dfs(ret,vis,pos+1);
//          vis[i]=false;
//      }
//  }
//  int main()
//  {
//      cin>>n;
//      vector<int> ret(n+1);
//      vector<bool> vis(n+1,0);
//      for(int i=1;i<=n;i++)cin>>ret[i];
//      dfs(ret,vis,1);
//      cout<<res<<endl;
//      return 0;
//  }

// n个数的全排列
//  const int n=3;
//  void dfs(vector<int>& ret,vector<bool>&vis)
//  {
//      if(ret.size()==n)
//      {
//          for(auto&x:ret)cout<<x<<" ";
//          cout<<endl;
//          return;
//      }
//      for(int i=1;i<=n;i++)
//      {
//          if(!vis[i])
//          {
//              vis[i]=true;
//              ret.push_back(i);
//              dfs(ret,vis);
//              ret.pop_back();
//              vis[i]=false;
//          }
//      }
//  }
//  int main()
//  {
//      vector<int> ret;
//      vector<bool> vis(n+1,0);
//      dfs(ret,vis);
//      return 0;
//  }

struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution
{
public:
    int sum=-1001;
    int dfs(TreeNode* root)
    {
        if(root==nullptr)return 0;
        int l=max(0,dfs(root->left));//统计左子树的最大单链和
        int r=max(0,dfs(root->right));//统计右子树的最大单链和
        sum=max(sum,root->val+l+r);//统计最大路径和
        //以我为根节点的最大单链和，如果返回的是最大路径和，就会导致重复计算
        //例如1，2，3 ，2为根节点，如果返回路径和6，在进行递归时走过的路就相当于2的根节点->2->1->3,不满足题目给的每个节点只出现一次
        return root->val+max(l,r);
    }
    int maxPathSum(TreeNode *root)
    {
        dfs(root);
        return sum;
    }
};